package ACWing.SearchAndGraphTheory.DFS;
//842. 排列数字

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/12/15 18:42
 */
public class StaggeredNumerals {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        ArrayList<Integer> list=new ArrayList<>();
        boolean[]arr=new boolean[n+1];
        dfs(list,n,arr);

    }
    public static void dfs(ArrayList<Integer> list,int n,boolean[]arr){
        if(list.size()==n){
            for (Integer integer : list) {
                System.out.print(integer+" ");

            }System.out.println();
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!arr[i]){
                list.add(i);
                arr[i]=true;
                dfs(list,n,arr);
                //恢复现场回归到上次的状态
                list.remove(list.size()-1);
                arr[i]=false;
            }
        }

    }
}
